package com.cc.od.monkey;

import java.util.Scanner;

/*
@description:
            题目描述
            孙悟空来到了蟠桃园偷吃蟠桃。蟠桃园有N棵桃树，每棵树上都有一定数量的蟠桃。守卫将在H小时后回来。孙悟空每小时可以选择吃一棵树上的所有蟠桃（如果数量少于他选择的速度，则全部吃掉），并且在这一个小时内不会吃其他树上的桃子。孙悟空希望以尽可能慢的速度吃蟠桃，但又要确保在守卫回来之前吃完所有的桃子。题目要求计算孙悟空能在H小时内吃完所有桃子的最小速度K（个/小时），如果以任何速度都吃不完，则返回0。

            输入描述
            第一行输入为N个数字，表示桃树的数量，接下来是N个数字，用空格分隔，表示每棵桃树上蟠桃的数量。
            第二行输入为一个数字H，表示守卫离开的时间（小时）。
            输出描述
            输出一个整数，表示孙悟空能在H小时内吃完所有桃子的最小速度K。如果以任何速度都吃不完，则输出0。
            解题思路
            这个问题可以通过二分查找算法来解决。因为速度K与吃完所有桃子所需的时间成反比，即速度越快，所需时间越少，这是一个单调关系。因此，可以通过二分查找找到满足条件的最小速度。

            确定二分查找的初始范围：最小速度可以设为1（即每小时至少吃一个桃子），最大速度可以设为桃树上最多蟠桃的数量。
            二分查找过程：
            在当前的速度范围内，选择一个中间速度mid。
            计算以这个速度吃完所有桃子所需的时间。
            如果所需时间小于等于H，说明这个速度或者更小的速度可能在H小时内吃完所有桃子，因此将搜索范围缩小到左半部分（即更小的速度）。
            如果所需时间大于H，说明这个速度无法在H小时内吃完所有桃子，因此需要尝试更大的速度，将搜索范围扩大到右半部分。
            结束条件：当搜索范围收敛到一个单独的速度时，该速度即为所求的最小速度K。
@ClassName MonkeyEatingPeaches
@author chen
@create 2024-09-29 17:14
@Version 1.0
*/
public class MonkeyEatingPeaches {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取桃树数量
        int N = scanner.nextInt();
        int[] peaches = new int[N];
        for (int i = 0; i < N; i++) {
            peaches[i] = scanner.nextInt();
        }
        // 读取守卫离开的时间（小时）
        int H = scanner.nextInt();

        // 调用函数计算最小速度
        int minSpeed = findMinEatingSpeed(peaches, H);

        if (minSpeed > 0) {
            System.out.println(minSpeed);
        } else {
            // 在这个特定问题中，由于每颗树上都有蟠桃，且H > 0，因此实际上不会输出0
            // 但为了代码的健壮性，还是保留了这个判断
            System.out.println("No solution possible (theoretically should not happen),0");
        }

    }

    private static int findMinEatingSpeed(int[] peaches, int H)
    {
        // 最小速度为1（因为速度不能为0）也就是一个小时吃一个桃子
        int left = 1;
        // 最大速度初始化为0，稍后在循环中更新
        int right = 0;
        for (int peach : peaches) {
            // 更新最大速度，确保它至少为树上最多的蟠桃数
            right = Math.max(right, peach);
        }
        while (left < right)
        {
            // 计算中间速度
            int mid = left + (right - left) / 2;
            if (canEatAllInHours(peaches, mid, H))
            {
                // 如果可以，尝试更小的速度
                right = mid;
            }
            else
            {
                // 如果不可以，需要更大的速度
                left = mid + 1;
            }
        }
        return left;
    }

    private static boolean canEatAllInHours(int[] peaches, int speed, int H)
    {
        // 总时间变量初始化为0
        int totalHours = 0;
        for (int peach : peaches) {
            // 计算吃掉当前桃子所需的时间，使用向上取整的方法确保精度
            totalHours += (peach + speed - 1) / speed;
        }

        return totalHours <= H;
    }
}
